#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
// 求数组长度
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
// 交换数组中的两个元素
#define SWAP(arr, i, j ) {			\
	int tmp = arr[i];			\
	arr[i] = arr[j];			\
	arr[j] = tmp;			\
}
// 打印数组的函数
void print_arr(int arr[], int left, int right) {
	for (int i = left; i <= right; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

// 分区是快速排序的核心逻辑
static int partition(int arr[], int left, int right) {
	// 1.直接选择left位置作为基准值，将基准值保存起来
	int pivot = arr[left];
	// 2.初始化两个索引，一个指向left，一个指向right
	int low = left, high = right;

	// 3.循环high索引先找到一个比基准值小的元素，然后移动覆盖到low位置，然后low++
	// 然后low索引再去找到一个比基准值大和相等的元素，然后移动覆盖到high位置，然后high--
	while (low < high){
		while (low < high && arr[high] >= pivot) {	// 这个=无所谓，快排不是稳定排序算法，都一样
			high--;
		}
		// high索引找到了比基准值小的元素
		arr[low] = arr[high];
		//low++;
		while (low < high && arr[low] < pivot) {
			low++;
		}
		// high索引找到了比基准值大和相等的元素
		arr[high] = arr[low];
		//high--;
	}
	// 4.循环结束时，high和low索引重合，此时重合位置就是pivot基准值最终的位置，将它插入该位置
	arr[low] = pivot;

	printf("pivot = %d  ", pivot);
	print_arr(arr, left, right);

	// 5.分区操作结束，返回这个基准值的下标
	return low;
}

static void partition_recursion(int arr[], int left, int right) {
	// 递归的出口
	if (left >= right) {
		return;
	}
	// 递归体
	int idx = partition(arr, left, right);
	partition_recursion(arr, left, idx - 1);
	partition_recursion(arr, idx + 1, right);
}


// 该函数就是对外提供接口，就是提供单向分区快排的功能
void quick_sort_two_way(int arr[], int len) {
	partition_recursion(arr, 0, len - 1);
}
int main(void) {
	// 测试双向分区快速排序
	int arr[] = { 8,3,2,6,9,5,10,20,30,1,3,5 };
	int len = ARR_LEN(arr);
	print_arr(arr, 0, len - 1);
	quick_sort_two_way(arr, len);
	return 0;
}